In an object-relational database, the world can be modeled using a type system fundamentally based on object types. An object type is associated with one or more attributes and zero or more methods. Instances of object types are known as "objects". Each object contains values for its attributes. The values of the attributes are collectively referred to as the object's state. Each object that is an instance of a particular object type has the same attributes. The methods associated with an object (i.e. methods associated with the object type of the object) operate upon the state of an object.
Object tables are tables that contain objects. Each object in an object table belongs to the same object type. More than one table may contain objects of a particular object type. For example, the tables FRIENDS and EMPLOYEES may both contain objects of the object type PERSON. Each row of data in a table stores the state of an object. Each column of an object table corresponds to an attribute of the objects contained in the object table.
For example, an object type called PERSON may define several attributes for objects which represent employees. Assume one attribute is NAME and another is SOCIAL SECURITY NUMBER. Further assume that an object table, EMPLOYEE, contains objects belonging to PERSON. One column in EMPLOYEE corresponds to the NAME attribute, another column corresponds to the SOCIAL SECURITY NUMBER attribute.
Each row in EMPLOYEE contains the state of one object. One row, for example, contains data for the object representing one employee with a NAME value of "John Doe" and having a SOCIAL SECURITY NUMBER value of "999-99-9999". One column in the row contains the value for the NAME attribute, and another column would contain the value for the SOCIAL SECURITY NUMBER attribute.
Objects may themselves be attributes of other objects. Consequently, a single object may appear at multiple places within a database. For example, the person object type may have a "children" attribute, where the children attribute is defined as a collection of person objects. Thus, assuming that a person X is the child of persons Y and Z, the object for person X may exist as a separate "person" object, as a component of the person Y object, and as a component of the person Z object.
It is inefficient to store multiple copies of an object at different places in an object-relational system. Therefore, separate copies of objects are typically not stored in the attribute portions of objects of which they are attributes. Instead, the attributes store data that identify objects, but not the objects themselves. Data that identifies an object is referred to as a "reference" to the object, and typically includes information that is used to locate the object.
In programming languages used with object-relational databases, such as PL/SQL.TM., it is desirable to provide users a mechanism for creating references to objects. For example, consider the following PL/SQL.TM. code fragment representing a declaration of a variable containing a reference.
DECLARE empref REF EMPLOYEE;
The code fragment declares the variable empref to be a reference to an object belonging to the object type EMPLOYEE. In response to this declaration, memory is allocated for storing a reference to an object belonging to EMPLOYEE. The data stored in that memory identifies a specific EMPLOYEE object and may be used to locate the EMPLOYEE object so that the object may be accessed.
One technique for generating references is referred to herein as the "object id" technique. In the object id technique, an object id is generated for and assigned to each object. An object id is a descriptor that uniquely, for all practical purposes, identifies an object. In an object-oriented database, such as the Oracle8 Database Server.TM., an object id is generated whenever an object is created in the database. Each reference to an object includes the object id for the object. When a reference is used to access an object, the object id is used to search the database for the object that has been assigned that object id.
One disadvantage suffered by the object id method is that every object table in a database must be examined for the object identified by the object id, until the sought object is found. Examining every object table until the sought object is found creates an undesirable amount of overhead.
One variation of the object id technique reduces the overhead of examining the object tables by using a single index table for the database. Each entry in the index table contains an object id and a table id, where the table id identifies the table that contains the object associated with the object id. To find the object associated with a reference using an index table, the index table is first searched to find the table associated with the object id contained in the reference. Once the appropriate table is identified, the table is searched based on the object id to locate the object associated with the reference.
Unfortunately, the use of a single index table for the whole database is not without its cost. The index table occupies a relatively large amount of data storage because it contains one entry for every object in the database. Relatively large tables, which require more work by the computer system to access and search, degrade performance. Furthermore, the index table is a single resource concurrently accessed by numerous transactions. Specifically, transactions that encounter any reference to any object in the database, transactions adding an object to a table, and transactions deleting an object each require access to the index table. As a consequence, access to the index table becomes a bottleneck and a source of numerous contention delays.
The problems described above are aggravated in a distributed environment, where objects may reside in any database of a number of databases. In a distributed environment, a client accessing a database first forms a "connection" to one of the databases. The database to which a client connects is referred to as the local database. Other databases are referred to as remote databases. Any table which resides on a remote database is referred to as a remote table, or a remote object table in the case of an object table. Often a remote database resides at a location remote to the local database. Because accessing data residing at a remote location consumes more computer resources and requires more time than accessing a data residing at a local location, access to remote tables on remote databases is expensive.
Thus the single index table approach is not practical for a distributed database. Because there is only one index table for the whole database (network), all accesses to distributed database objects depend on access to a single index table in a database. This causes performance, availability, and scalability problems (i.e. the number of users is constrained by performance related problems arising from the single index approach).
It is clearly desirable to provide a method for more efficiently referencing objects that are stored in an object-relational database system.